/**
  * @file    :LinkQueue.hpp
  * @brief   :链队的模板类
  * @author  :TMJ
  * @version :V1.0.0
  * @date    :2023-12-27
*/

#ifndef _QUEUE_LINKQUEUE_H_
#define _QUEUE_LINKQUEUE_H_

#include "Queue.hpp"
#include <iostream>


template<typename type>
class LinkQueueNode {

public:
    // 默认构造函数
    LinkQueueNode() : next(nullptr) {}

    // 指定指针域的构造函数
    explicit LinkQueueNode(class LinkQueueNode<type> *next = nullptr) : next(next) {}

    // 指定参数构造函数
    explicit LinkQueueNode(const type &data, class LinkQueueNode<type> *next = nullptr) : data(data), next(next) {}

    // 获取结点数据
    type GetData() const {
        return this->data;
    }

    // 设置结点数据
    void SetData(const type &data) {
        this->data = data;
    }

    // 获取指针域
    LinkQueueNode<type> *Next() const {
        return this->next;
    }

    // 设置指针域
    void SetNext(LinkQueueNode<type> *const &next) {
        this->next = next;
    }

private:
    type data;                       // 数据域
    struct LinkQueueNode<type> *next;// 指针域
};

template<typename type>
class LinkQueue;

template<typename type>
std::ostream &operator<<(std::ostream &out, const LinkQueue<type> &src);

template<typename type>
class LinkQueue : public Queue<type> {

    friend std::ostream &operator<<<>(std::ostream &out, const LinkQueue<type> &src);

public:
    // 默认构造函数
    LinkQueue() : _front(nullptr), _rear(nullptr) {};

    // 析构函数
    ~LinkQueue() {
        Clear();
    }

    // 清空队列
    void Clear();

    // 入队
    virtual bool EnQueue(const type &data);

    // 出队
    virtual bool DeQueue(type &data);

    // 出队(不保存数据)
    virtual bool DeQueue();

    // 获取队头元素
    virtual bool Front(type &data) const;

    // 判断队空
    virtual bool IsEmpty() const;

    // 获取队列长度
    virtual int Length() const;

private:
    // 获取头节点
    LinkQueueNode<type> *_FrontNode() const {
        return this->_front;
    }

    // 获取尾节点
    LinkQueueNode<type> *_RearNode() const {
        return this->_rear;
    }

    LinkQueueNode<type> *_front;// 头指针
    LinkQueueNode<type> *_rear; // 尾指针
};

// 清空队列
template<typename type>
void LinkQueue<type>::Clear() {
    while (!IsEmpty()) {
        DeQueue();
    }
}

// 入队
template<typename type>
bool LinkQueue<type>::EnQueue(const type &data) {
    auto *newNode = new LinkQueueNode<type>(data);
    if (!newNode) {
        return false;
    }

    if (IsEmpty()) {
        _front = newNode;
        _rear = newNode;
    } else {
        _rear->SetNext(newNode);
        _rear = newNode;
    }

    return true;
}

// 出队(保存数据)
template<typename type>
bool LinkQueue<type>::DeQueue(type &data) {
    // 非法处理
    if (IsEmpty()) {
        return false;
    }

    LinkQueueNode<type> *del = _front;
    data = del->GetData();
    _front = del->Next();

    delete del;
    del = nullptr;

    return true;
}

// 出队(不保存数据)
template<typename type>
bool LinkQueue<type>::DeQueue() {
    // 非法处理
    if (IsEmpty()) {
        return false;
    }

    LinkQueueNode<type> *del = _front;
    _front = _front->Next();

    delete del;

    return true;
}

// 获取队头元素
template<typename type>
bool LinkQueue<type>::Front(type &data) const {
    // 非法处理
    if (IsEmpty()) {
        return false;
    }

    data = _front->GetData();

    return true;
}

// 判断队空
template<typename type>
bool LinkQueue<type>::IsEmpty() const {
    return this->_front == nullptr;
}

// 获取队列长度
template<typename type>
int LinkQueue<type>::Length() const {
    int size = 0;

    for (LinkQueueNode<type> *cur = _front; cur != nullptr; cur = cur->Next()) {
        size++;
    }

    return size;
}

// 重载 << 运算符
template<typename type>
std::ostream &operator<<(std::ostream &out, const LinkQueue<type> &src) {
    out << "The size of link queue: " << src.Length() << std::endl;

    LinkQueueNode<type> *cur = src._FrontNode();

    for (int i = 1; cur != nullptr; i++) {
        out << i << ":" << cur->GetData() << std::endl;
        cur = cur->Next();
    }

    return out;
}


#endif// _QUEUE_LINKQUEUE_H_